package slidingWindow;

import java.util.HashSet;
import java.util.Set;

@Deprecated
public class SlidingWindow05 {

    /**
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
     *
     * @param args
     */
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow02(s, t));
    }

    public static String minWindow(String s, String t){
        int s_len = s.length();
        int t_len = t.length();
        int minLen = Integer.MAX_VALUE;
        int begin = 0;
        //创建存放t中字符的hash
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        for (int i = 0; i < t_len; i++){
            set1.add(t.charAt(i));
        }
        set2.addAll(set1);

        int left = 0;
        for (int right = 0; right < s_len; right++){
            //处理右边界
            if (set2.contains(s.charAt(right))){
                set2.remove(s.charAt(right));
            }
            if (set2.size()==0){
                if (minLen > right - left+1){
                    minLen = right - left+1;
                    begin = left;
                }
            }
            //处理左边界
            while ((set2.size() == 0 || !set1.contains(s.charAt(left))) && left < s_len){
                if (set1.contains(s.charAt(left))){
                    set2.add(s.charAt(left));
                }
                left++;
            }
        }
        if (minLen == Integer.MAX_VALUE){
            return "";
        } else {
            return s.substring(begin, begin + minLen);
        }

    }

    public static String minWindow02(String s, String t){
        int s_len = s.length();
        int t_len = t.length();
        int minLen = Integer.MAX_VALUE;
        int begin = 0;
        //创建存放t中字符的hash
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        for (int i = 0; i < t_len; i++){
            set1.add(t.charAt(i));
        }
        set2.addAll(set1);

        int right = 0;
        //初始化右边界
        if (set2.contains(s.charAt(right))){
            set2.remove(s.charAt(right));
        }
        for (int left = 0; left < s_len; left++){
            //处理右边界
            while (right+1 < s_len && set2.size() > 0){
                right++;
                if (set2.contains(s.charAt(right))){
                    set2.remove(s.charAt(right));
                }
            }
            //只有满足条件才收集结果
            if (set2.size() == 0){
                if (minLen > right-left+1){
                    minLen = right-left+1;
                    begin = left;
                }
            }
            //处理左边界
            if (set1.contains(s.charAt(left))){
                set2.add(s.charAt(left));
            }

        }
        if (minLen == Integer.MAX_VALUE){
            return "";
        } else {
            return s.substring(begin, begin + minLen);
        }
    }
}
